Package edu.claflin.finder.logic.communities.struct

Class BinarySearchTree<T extends TreeNodeInfo>

java.lang.Object

edu.claflin.finder.logic.communities.struct.BinarySearchTree<T>

public class BinarySearchTree<T extends TreeNodeInfo>
extends java.lang.Object

Field Summary

Fields

Modifier and Type	Field	Description
private boolean	allow_duplicates
private TreeNode<T>	root

Constructor Summary

Constructors

Constructor	Description
BinarySearchTree()	Create an empty BinarySearchTree.
BinarySearchTree(boolean dup)

Method Summary

Modifier and Type	Method	Description
void	add(T info)	Addd a new Tree Node with the given j index and q value
private void	add(T info, TreeNode<T> p)	Recursive implementation of add.
boolean	allows_duplicates()
java.util.List<T>	asList()
private void	asList(java.util.List<T> l, TreeNode<T> p)
void	clear()
boolean	contains(T info)	Is the specified ElemntType in the BinarySearchTree?
private boolean	contains(T info, TreeNode<T> p)
private void	createBackbone()	Time complexity: O(n)
private void	createPerfectBST()	Time complexity: O(n)
void	DSW()
T	get(T info)
private TreeNode<T>	get(T info, TreeNode<T> p)
int	getHeight()
private int	getHeight(TreeNode<T> p)
T	getMax()
T	getMax(TreeNode<T> p)
T	getMin()
private T	getMin(TreeNode<T> p)
java.lang.Double	getVal(T info)
private int	greatestPowerOf2LessThanN(int n)	.
boolean	isEmpty()	Is the BinarySearchTree empty?
private void	makeRotations(int bound)
void	mergeTrees(BinarySearchTree that)
private void	mergeTrees(BinarySearchTree that, TreeNode<T> p)
int	MSB(int n)	Return the index of most significant set bit: index of least significant bit is 0.
void	remove(T info)
private TreeNode<T>	remove(T info, TreeNode<T> p)
private void	rotateLeft(TreeNode<T> grandParent, TreeNode<T> parent, TreeNode<T> rightChild)
private TreeNode<T>	rotateRight(TreeNode<T> grandParent, TreeNode<T> parent, TreeNode<T> leftChild)
void	set(T info)
java.lang.String	toString()	Gets an inorder String representation of the BinarySearchTree.
private java.lang.String	toString(TreeNode<T> p)	Recursive implementation of inorder toString.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

root

private TreeNode<T extends TreeNodeInfo> root

allow_duplicates

private boolean allow_duplicates

Constructor Detail

BinarySearchTree

public BinarySearchTree()

Create an empty BinarySearchTree.

BinarySearchTree

public BinarySearchTree(boolean dup)

Method Detail

allows_duplicates

public boolean allows_duplicates()

isEmpty

public boolean isEmpty()

Is the BinarySearchTree empty?

Returns:

true if empty, false otherwise

clear

public void clear()

add

public void add(T info)

Addd a new Tree Node with the given j index and q value

Parameters:

info - the key

add

private void add(T info,
                 TreeNode<T> p)

Recursive implementation of add.

Parameters:

info - the key

p - the current top Tree Node

getVal

public java.lang.Double getVal(T info)

get

public T get(T info)

get

private TreeNode<T> get(T info,
                        TreeNode<T> p)

set

public void set(T info)

contains

public boolean contains(T info)

Is the specified ElemntType in the BinarySearchTree?

Parameters:

info - the key

Returns:

true if it is contained, false otherwise

contains

private boolean contains(T info,
                         TreeNode<T> p)

toString

public java.lang.String toString()

Gets an inorder String representation of the BinarySearchTree.

Overrides:

toString in class java.lang.Object

Returns:

the BinarySearchTree as a String

toString

private java.lang.String toString(TreeNode<T> p)

Recursive implementation of inorder toString.

Parameters:

p - the current TreeNode to print and recursive parameter

Returns:

the BinarySearchTree as a String

getMin

public T getMin()

getMin

private T getMin(TreeNode<T> p)

getMax

public T getMax()

getMax

public T getMax(TreeNode<T> p)

remove

public void remove(T info)

remove

private TreeNode<T> remove(T info,
                           TreeNode<T> p)

getHeight

public int getHeight()

getHeight

private int getHeight(TreeNode<T> p)

DSW

public void DSW()

createBackbone

private void createBackbone()

Time complexity: O(n)

rotateRight

private TreeNode<T> rotateRight(TreeNode<T> grandParent,
                                TreeNode<T> parent,
                                TreeNode<T> leftChild)

createPerfectBST

private void createPerfectBST()

Time complexity: O(n)

greatestPowerOf2LessThanN

private int greatestPowerOf2LessThanN(int n)

. Time complexity: log(n)

Parameters:

n - the inout number

Returns:

the greatest power of 2 less than N

MSB

public int MSB(int n)

Return the index of most significant set bit: index of least significant bit is 0. Time complexity: log(n)

Parameters:

n - the input number

Returns:

the index of most significant set bit

makeRotations

private void makeRotations(int bound)

rotateLeft

private void rotateLeft(TreeNode<T> grandParent,
                        TreeNode<T> parent,
                        TreeNode<T> rightChild)

mergeTrees

public void mergeTrees(BinarySearchTree that)

mergeTrees

private void mergeTrees(BinarySearchTree that,
                        TreeNode<T> p)

asList

public java.util.List<T> asList()

asList

private void asList(java.util.List<T> l,
                    TreeNode<T> p)